#include <stdio.h>
#include <stdlib.h>
#include <stack.h>

typedef struct BSTreeNode_	/* a node in the binary search tree - BST */
{
    int val;			/* value of node */
    struct BSTreeNode_ *left;		/* left child of node */
    struct BSTreeNode_ *right;		/* right child of node */
} Node;

void swap(Node **left, Node **right)
{
    Node *pNode = *left;
    *left = *right;
    *right = pNode;
}

void mirror(Node *root)
{
    if (NULL == root)
	return;

    swap(&(root->left), &(root->right));
    if (root->left != NULL)
	mirror(root->left);
    if (root->right != NULL)
	mirror(root->right);
}

void mirrorIteratively(Node *root)
{
    if (NULL == root)
	return;
    
    Stack stack;
    stack_init(&stack, NULL);
    stack_push(&stack, root);

    Node *pNode;
    while (stack_size(&stack) != 0) {
	stack_pop(&stack, (void **)&pNode);
	swap(&(pNode->left), &(pNode->right));
	if (pNode->left != NULL)
	    stack_push(&stack, pNode->left);
	if (pNode->right != NULL)
	    stack_push(&stack, pNode->right);
    }
    stack_destroy(&stack);
}

void visit(Node *pNode)
{
    if (pNode != NULL)
	printf(" %d", pNode->val);
}

void preorder(Node *root)
{
    if (NULL == root)
	return;

    visit(root);
    preorder(root->left);
    preorder(root->right);
}

void inorder(Node *root)
{
    if (NULL == root)
	return;

    inorder(root->left);
    visit(root);
    inorder(root->right);
}

void postorder(Node *root)
{
    if (NULL == root)
	return;

    postorder(root->left);
    postorder(root->right);
    visit(root);
}

int main()
{
    int a[] = {8, 6, 10, 5, 7, 9, 11};
    /* int len = sizeof(a)/sizeof(int); */
    Node bst[7];

    for (int i = 0; i < 7; ++i) {
	bst[i].val = a[i];
	bst[i].left = NULL;
	bst[i].right = NULL;
    }
    
    for (int i = 0; i < 3; ++i) {
	bst[i].left = &bst[2*i + 1];
	bst[i].right = &bst[2*i + 2];
    }

    /* mirror(bst); */
    mirrorIteratively(bst);

    for (int i = 0; i < 7; ++i) {
	printf("%d ", bst[i].val);
    }
    printf("\n");

    preorder(bst);
    printf("\n");
    inorder(bst);
    printf("\n");
    postorder(bst);
    printf("\n");

    exit(0);
}
